Theory of Computation
---------------------

<!--
SPDX-FileCopyrightText: Chris Pressey, the original author of this work, has dedicated it to the public domain.

SPDX-License-Identifier: CC0-1.0
-->

[(Up)](../../README.md#topics) | _See also: [Computational Complexity](../Computational%20Complexity/README.md#computational-complexity), [Automata Theory](../Automata%20Theory/README.md#automata-theory), [Formal Language](../Formal%20Language/README.md#formal-language)_

- - - -


### Web resources

[Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?](https://cs.stackexchange.com/questions/168182/why-is-the-turing-machine-considered-effective-computation-if-its-not-realizabl) ★

[Other Undecidable Problems (wayback)](https://web.archive.org/web/20210507040412/https://www.cs.wcupa.edu/rkline/fcs/other-undecidable.html) ★

[Scooping the Loop Snooper --- Geoffrey K. Pullum](http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html) ★

[Shtetl-Optimized » Blog Archive » Rosser's Theorem via Turing machines](https://www.scottaaronson.com/blog/?p=710) ★

[Are there any undecidability results that are not known to have a diagonal argument proof?](https://mathoverflow.net/questions/454105/are-there-any-undecidability-results-that-are-not-known-to-have-a-diagonal-argum) ★

[Is there a finite-dimensional vector space whose dimension cannot be found?](http://mathoverflow.net/questions/77068/is-there-a-finite-dimensional-vector-space-whose-dimension-cannot-be-found) ★

### Algorithmic Information Theory

[The Limits of Reason (Gregory Chaitin)](https://web.archive.org/web/20140812152541/https://www.cs.auckland.ac.nz/~chaitin/sciamer3.html) ★

_(in [Automata Theory](../Automata%20Theory/README.md#automata-theory))_ [Turing Machines (William Shoaf, 2001, pdf)](https://web.archive.org/web/20120514172528/http://www.cs.fit.edu/~wds/classes/complexity/lct/turing.pdf) ★

_(in [Automata Theory](../Automata%20Theory/README.md#automata-theory))_ [Csc520 Foundations of Computer Science](https://web.archive.org/web/20161105235418/https://www.cs.wcupa.edu/rkline/csc520) ★

_(in [Computational Complexity](../Computational%20Complexity/README.md#computational-complexity))_ [Computability and Complexity (Stanford Encyclopedia of Philosophy)](https://plato.stanford.edu/entries/computability/) ★★★

_(in [Computational Complexity](../Computational%20Complexity/README.md#computational-complexity))_ [Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science](http://theoryofcomputing.org/) ★ [💭](commentary/Chris%20Pressey.md#theory-of-computing-an-open-access-electronic-journal-in-theoretical-computer-science)


### Books

Computation: Finite and Infinite Machines (borrow @ [archive.org](https://archive.org/details/computationfinit0000mins)) 🏛️ [💭](commentary/Chris%20Pressey.md#computation-finite-and-infinite-machines)

The Universal Turing Machine (borrow @ [archive.org](https://archive.org/details/universalturingm0000unse)) ★★★ [💭](commentary/Chris%20Pressey.md#the-universal-turing-machine)

Theory of Recursive Functions and Effective Computability (borrow @ [archive.org](https://archive.org/details/theoryofrecursiv00roge)) [💭](commentary/Chris%20Pressey.md#theory-of-recursive-functions-and-effective-computability)

Automata and Computability (borrow @ [archive.org](https://archive.org/details/automatacomputab0000koze)) ★ [💭](commentary/Chris%20Pressey.md#automata-and-computability)

Theory of Computation (borrow with print disabilities @ [archive.org](https://archive.org/details/theoryofcomputat00brai), [archive.org](https://archive.org/details/theoryofcomputat0000brai)) [💭](commentary/Chris%20Pressey.md#theory-of-computation)

Theories of Computation (borrow @ [archive.org](https://archive.org/details/theoriesofcomput0000pipp)) ★ [💭](commentary/Chris%20Pressey.md#theories-of-computation)

Computability Theory, Semantics, and Logic Programming (borrow @ [archive.org](https://archive.org/details/computabilitythe0000fitt)) [💭](commentary/Chris%20Pressey.md#computability-theory-semantics-and-logic-programming)

Theory of Deductive Systems and its Applications (borrow @ [archive.org](https://archive.org/details/TheoryofDe_00_Masl)) ★★★ [💭](commentary/Chris%20Pressey.md#theory-of-deductive-systems-and-its-applications)

_(in [Formal Language](../Formal%20Language/README.md#formal-language))_ Introduction to Formal Languages (borrow @ [archive.org](https://archive.org/details/introductiontofo0000reve)) ★ [💭](commentary/Chris%20Pressey.md#introduction-to-formal-languages)

_(in [Formal Language](../Formal%20Language/README.md#formal-language))_ Programs, Grammars, Arguments (online @ [archive.org](https://archive.org/details/flooved3381))

_(in [Logic](../Logic/README.md#logic))_ Mathematical Logic (Kleene) (borrow @ [archive.org](https://archive.org/details/mathematicallogi0000klee)) 🏛️ [💭](commentary/Chris%20Pressey.md#mathematical-logic-kleene)